package com.itheima.leetcode.od.b.bf;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.TreeSet;
import java.util.stream.Collectors;

/**
 * (A卷,100分)- 端口合并（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 有M个端口组(1<=M<=10)，
 * 每个端口组是长度为N的整数数组(1<=N<=100)，
 * 如果端口组间存在2个及以上不同端口相同，则认为这2个端口组互相关联，可以合并。
 * <p>
 * 输入描述
 * <p>
 * 第一行输入端口组个数M，再输入M行，每行逗号分割，代表端口组。
 * <p>
 * 备注：端口组内数字可以重复。
 * <p>
 * 输出描述
 * <p>
 * 输出合并后的端口组，用二维数组表示。
 * <p>
 * 组内相同端口仅保留一个，从小到大排序。
 * 组外顺序保持输入顺序
 * 备注：M,N不在限定范围内，统一输出一组空数组[[]]
 * <p>
 * 用例
 * <p>
 * 输入	4
 * 4
 * 2,3,2
 * 1,2
 * 5
 * 输出	[[4],[2,3],[1,2],[5]]
 * 说明	仅有一个端口2相同，不可以合并。
 * 输入	3
 * 2,3,1
 * 4,3,2
 * 5
 * 输出	[[1,2,3,4],[5]]
 * 说明	无
 * 输入	6
 * 10
 * 4,2,1
 * 9
 * 3,6,9,2
 * 6,3,4
 * 8
 * 输出	[[10],[1,2,3,4,6,9],[9],[8]]
 * 说明	无
 * 输入	11
 * 输出	[[]]
 * 说明	无
 * 题目解析
 * 本题有一个疑点：
 * <p>
 * 如果端口组间存在2个及以上不同端口相同，则认为这2个端口组互相关联，可以合并。
 * <p>
 * 那就是上面这句话中“不同端口”指的是什么？
 * <p>
 * 比如下面用例中两个端口组都有端口3 3，那么是否可以合并呢？
 * <p>
 * 2
 * 3 3 5
 * 1 3 3
 * <p>
 * 我们假设 a = [3,3,5]，b = [1,3,3]，那么a[0]和b[1]相同，a[1]和b[2]相同，这种端口所在位置不同，但是端口值相同的，是否也能算2个不同端口相同呢？
 * <p>
 * 这里搞不清楚，就会产生两种解题思路：
 * <p>
 * 1、两个端口组，如果可以形成2对端口值相同的端口对，那么也可以合并
 * <p>
 * 2、两个端口组，只有形成2对端口值不同的端口对，那么才可以合并
 * <p>
 * 如果能形成2个端口值相同的端口对，那么也可以合并
 */
public class CanUnion {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int m = Integer.parseInt(sc.nextLine());

        // M,N不在限定范围内，统一输出一组空数组[[]]
        if (m > 10 || m < 1) {
            System.out.println("[[]]");
            return;
        }*/

        // 这里使用ArrayList接收端口组，是为了后面更方便进行端口组之间的合并
        ArrayList<ArrayList<Integer>> ports = Arrays.stream("4\n2,3,2\n1,2\n5".split("\n"))
                .map(s -> Arrays.stream(s.split(","))
                        .mapToInt(Integer::valueOf)
                        .boxed()
                        .collect(Collectors.toCollection(ArrayList::new)))
                .collect(Collectors.toCollection(ArrayList::new));

        System.out.println(getResult(ports));
    }

    // 算法入口 (双指针)
    public static String getResult(ArrayList<ArrayList<Integer>> ports) {
        outer:
        while (true) {
            // 这里倒序组合遍历端口组是为了实现：组外顺序保持输入顺序（因为这样remove代码运算效率高）
            for (int i = ports.size() - 1; i >= 0; i--) {
                for (int j = i - 1; j >= 0; j--) {

                    // 判断两个端口是否可以合并
                    if (canUnion(ports.get(i), ports.get(j))) {
                        // 将后面的端口组，并入前面的端口组，这样就不会破坏组外顺序
                        ports.get(j).addAll(ports.get(i));
                        ports.remove(i);
                        continue outer;
                    }
                }
            }

            break;
        }

        return ports.stream()
                .map(port -> new TreeSet<Integer>(port).stream()
                        .map(String::valueOf)
                        .collect(Collectors.joining(",", "[", "]")))
                .collect(Collectors.joining(",", "[", "]"));
    }

    // 如果端口组间存在2个及以上不同端口相同，则认为这2个端口组互相关联，可以合并。
    // 下面方法实现中：对于“不同端口”的理解是：端口位置不同，端口值可以相同，即以不同位置的端口视为不同端口
    public static boolean canUnion(ArrayList<Integer> port1, ArrayList<Integer> port2) {
        port1.sort((a, b) -> a - b);
        port2.sort((a, b) -> a - b);

        int same = 0;
        int i = 0;
        int j = 0;

        while (i < port1.size() && j < port2.size()) {
            if (port1.get(i) - port2.get(j) == 0) {
                i++;
                j++;
                if (++same >= 2) {
                    return true;
                }
            } else if (port1.get(i) > port2.get(j)) {
                j++;
            } else {
                i++;
            }
        }

        return false;
    }
}
